import java.util.Random;

public class QuickSort {

    private QuickSort() {}

    // 单路快速排序
    // 单路快速排序的问题： 对于有序样本，性能会从O(nlogN)退化到O(n^2), 加入随机pivot选择可以解决
    public static <E extends Comparable<E>> void sortV1(E[] data) { sortV1(data, 0, data.length - 1);}
    public static <E extends Comparable<E>> void sortV1(E[] data, int l, int r) {
        if (l >= r) return;
        int p = partition(data, l, r);
        sortV1(data, l, p - 1);
        sortV1(data, p + 1, r);
    }
    // 要点： partition 过程
    private static <E extends Comparable<E>> int partition(E[] data, int l, int r) {
        // int pivot;   // pivot = 标定点
        // ============================================================
        // 优化解决顺序数据样本的退化问题， 对于相同元素样本，则需要双路快速排序解决
        int pivot = (new Random()).nextInt(r -l + 1) + l;
        SortingHelper.swap(data, pivot, l); // 将标定点交换到起始位置
        // ============================================================
        int j = l;
        for (int i = l + 1; i <= r; i++) {
            if (data[i].compareTo(data[l]) <= 0) {
                SortingHelper.swap(data, i, j + 1);
                j++;
            }
        }
        SortingHelper.swap(data, l, j);
        return j;
    }



    // 双路快速排序
    public static <E extends Comparable<E>> void sortV2(E[] data) { sortV2(data, 0, data.length - 1);}
    public static <E extends Comparable<E>> void sortV2(E[] data, int l, int r) {
        if (l >= r) return;

        int pivot = partition2(data, l, r);
        sortV2(data, l, pivot - 1);
        sortV2(data, pivot + 1, r);
    }

    // 双路快速排序的partition过程， 解决了重复元素样本的问题
    // TODO 还有问题，需要修改
    private static <E extends Comparable<E>> int partition2(E[] data, int l, int r) {
        int pivot = l;
        int i = l + 1;
        int j = r;
        while (true) {
            while (data[j].compareTo(data[pivot]) >= 0 && i < j) j--;
            while (data[i].compareTo(data[pivot]) <= 0 && i < j) i++;
            SortingHelper.swap(data, i, j);
            if (i >= j) break;
        }
        SortingHelper.swap(data, pivot, j);
        return j;
    }

    // 三路快速排序
    public static <E extends Comparable<E>> void sortV3(E[] data) { sortV3(data, 0, data.length - 1);}
    public static <E extends Comparable<E>> void sortV3(E[] data, int l, int r) {

    }


}
